/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 28463
 * Date: 2022—05—09
 * Time: 12:05
 */
class Solution {

    int firstBadVersion(int n) {
        int left = 1, right = n;
        while (left < right) { // 循环直至区间左右端点相同
            int mid = left + (right - left) / 2; // 防止计算时溢出
            if (isBadVersion(mid)) {
                right = mid; // 答案在区间 [left, mid] 中
            } else {
                left = mid + 1; // 答案在区间 [mid+1, right] 中
            }
        }
        // 此时有 left == right，区间缩为一个点，即为答案
        return left;
    }

    private boolean isBadVersion(int mid) {
    }
};

class Solution {

    public int[] searchRange(int[] nums, int target) {
        int leftBorder = getLeftBorder(nums, target);
        int rightBorder = getRightBorder(nums, target);
        if(leftBorder == -2 || rightBorder == -2){
            return new int[]{-1,-1};
        }
        if(rightBorder -leftBorder >1){
            return new int[]{leftBorder + 1,rightBorder - 1};
        }
        return new int[]{-1,-1};
    }
    public int getLeftBorder(int[] nums, int target){
        int left = 0;
        int right = nums.length - 1;
        int leftBorder = -2;//用来记录leftBorder没有被赋值的情况
        while(left <= right){
            int mid = left + (right - left);
            if(nums[mid] >= target){
                //寻找左边界
                right = mid - 1;
                leftBorder = right;
            }else{
                left = mid + 1;
            }
        }
        return leftBorder;
    }
    public int getRightBorder(int[] nums, int target){
        int left = 0;
        int right = nums.length - 1;
        int rightBorder = -2;
        while(left <= right){
            int mid = left + (right - left);
            if(nums[mid] > target){
                right = mid - 1;
            }else{
                //寻找右边界
                left = mid + 1;
                rightBorder = left;
            }
        }
        return rightBorder;
    }
}
class Solution {
    public int mySqrt(int x) {
        int l = 0, r = x, ans = -1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if ((long) mid * mid <= x) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }
}
class Solution {
    public boolean isPerfectSquare(int num) {
        int left = 0, right = num;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            long square = (long) mid * mid;
            if (square < num) {
                left = mid + 1;
            } else if (square > num) {
                right = mid - 1;
            } else {
                return true;
            }
        }
        return false;
    }
}


public class TestDemo01 {

}
